\def\lecture{22}
\clearpage \noindent\begin{tabularx}{\linewidth}{|X|}
\hline \vskip -2mm
{\sf 编译原理} \hfill November 18, 2011 \\
{\centering \sf \large Lecture \lecture:
符号表的讨论 \\ }
\textsl{Lecturer: 冯博琴 \hfill Scriber: 戴唯思}\\ \hline
\end{tabularx}
\setcounter{section}{0}
\renewcommand{\thepage}{\lecture -\arabic{page}}

\section{符号表}

    \subsection{符号表的内容}

        \paragraph{符号表要实现的功能} 查找判断存在性, 查找获取信息, 填入, 更新, 删除.

        基本形态: 变量名, 变量信息. 采用分表的方式方便随机访问.

    \subsection{符号表的原理和实现}

        组织方案: 线性表, 折半查找, 哈希表. 此外还要解决冲突问题, 因此需要引入探查机制: (内部解决) 线性探查法(开放探查法), 二次探查法, 平方探查法, (外部解决) 链表法, \ldots

        \paragraph{关于哈希表的讨论}

            总时间$=$计算时间$I$+查找长度. 因此尽量减小查找长度.

    \subsection{符号的作用域}

        Fortran语言采用模块结构, 存在局部和全局作用域层次, 采用双向对开线性表实现. 分层的稍微难一点, 源自ALGOL语言: \textsf{最近嵌套原则}.
